package Heap.LeetCode;

import java.util.*;

public class Num373_kSmallestPairs {
    private class Pair{
        int u;
        int v;

        public Pair(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //扫描这两个数组 u这个元素来自第一个数组 v这个元素来自第二个数组
        //最大堆pair，此时元素的大小关系为u+v的值越大认为元素越大
        Queue<Pair> queue=new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            //改造为最大堆
            public int compare(Pair o1, Pair o2) {
                return (o2.v+o2.u)-(o1.v+o1.u);
            }
        });
        //2.遍历数组
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if(queue.size()<k){
                    queue.offer(new Pair(nums1[i],nums2[j] ));
                }else{
                    int add=nums1[i]+nums2[j];
                    Pair pair=queue.peek();
                    if(add>(pair.u+ pair.v)){
                        continue;
                    }else{
                        queue.poll();
                        queue.offer(new Pair(nums1[i],nums2[j] ));
                    }
                }
            }
        }
        //此时优先级队列中就存储了和最小的前k个pair对象
        List<List<Integer>> ret=new ArrayList<>();
        for (int j = 0; j < k&&(!queue.isEmpty()); j++) {
            List<Integer> temp=new ArrayList<>();
            Pair pair=queue.poll();
            temp.add(pair.u);
            temp.add(pair.v);
            ret.add(temp);
        }
        return ret;
    }
}
